#include <iostream>
#include <string>
#include <stack>

using namespace std;

class Node{
public:
	string _value;
	Node *left;
	Node *right;

public:
	Node(string value) : _value(value), left(NULL), right(NULL){}
};

typedef Node* BTree;

Node *findFirstPublicNode(BTree root, Node *nodeA, Node *nodeB){


	return NULL;
}

void findParentNodes(BTree root, const Node *node, Node **parents){
	if(NULL == root || NULL == node)
		return;
	if(node == root->left || node == root->right){
		*parents = new Node("ParentListTail");
		(*parents)->left = root;
		(*parents)->right = root;
		return;
	}
	findParentNodes(root->left, node, parents);
	findParentNodes(root->right, node, parents);
}

bool findParentNodes(BTree root, const Node *node, stack<BTree> &parents){
	if(NULL == root || NULL == node)
		return false;
	bool result = false;
	if(node == root->left || node == root->right){
		parents.push(root);
		return true;
	}
	result |= findParentNodes(root->left, node, parents);
	result |= findParentNodes(root->right, node, parents);
	if(result)
		parents.push(root);
	return result;
}

int ffpmain(){
	BTree root = new Node("root");

	root->left = new Node("A");	
	root->right = new Node("B");

	root->left->left = new Node("C");
	root->left->right = new Node("D");
	root->right->left = new Node("E");
	root->right->right = new Node("F");

	root->left->left->left = new Node("G");
	root->left->left->right = new Node("H");
	root->left->right->left = new Node("I");
	root->left->right->right = new Node("J");
	root->right->left->left = new Node("K");
	root->right->left->right = new Node("L");
	root->right->right->left = new Node("M");
	root->right->right->right = new Node("N");
	
	/*Node *parents = NULL;
	findParentNodes(root, root->left->left, &parents);
	*/
	stack<Node*> parentStack;
	findParentNodes(root, root->left->right->right, parentStack);

	return 0;
}